package swardToOffer.struct_3_linkedlist;

/**
 * @Author ChanZany
 * @Date 2021/5/21 16:28
 * @Version 1.0
 * <p>
 * 面试题25：合并两个排序的链表
 * 题目：【输入两个递增排序的链表】，合并这两个链表并使新链表中的结点仍然是按照递增排序的。
 * 例如输入图3.11中的链表1和链表2，则合并之后的升序链表如链表3所示。
 * <p>
 * 归并排序的合并思想
 * 用两个指针p1/p2分别指向两个链表的头
 * 比较p1和p2所在元素的大小，小的元素添加到临时链表中，并且指针后移
 * 继续比较直到某个链表被遍历完
 * 还有一个链表没有被遍历完，则将后面的元素依次复制到临时链表中
 */
public class MergeSortedLists {
    ListNode merge(ListNode head1, ListNode head2) {
        if (head1 == null || head2 == null) return null;
        ListNode p1 = head1;
        ListNode p2 = head2;
        ListNode p3 = new ListNode();
        ListNode tmp = p3;
        while (p1 != null && p2 != null) {
            if (p1.val < p2.val) {
                tmp.next = p1;
                tmp = tmp.next;
                p1 = p1.next;
            } else {
                tmp.next = p2;
                tmp = tmp.next;
                p2 = p2.next;
            }
        }
        while (p1 != null) {
            tmp.next = p1;
            tmp = tmp.next;
            p1 = p1.next;
        }
        while (p2 != null) {
            tmp.next = p2;
            tmp = tmp.next;
            p2 = p2.next;
        }
        return p3.next;
    }

    //与树的创建有异曲同工之妙
    ListNode mergeImprove(ListNode head1, ListNode head2) {
        if (head1 == null || head2 == null) return null;
        ListNode mergedHead = null;
        if (head1.val < head2.val) {
            mergedHead = head1;
            mergedHead.next = mergeImprove(head1.next, head2);
        } else {
            mergedHead = head2;
            mergedHead.next = mergeImprove(head1, head2.next);
        }
        return mergedHead;
    }

    public static void main(String[] args) {
        ListNode head1 = LinkedListUtils.buildLinkedList(new int[]{1, 3, 5, 7});
        ListNode head2 = LinkedListUtils.buildLinkedList(new int[]{2, 4, 6, 8});
        MergeSortedLists Main = new MergeSortedLists();
//        ListNode res1 = Main.merge(head1, head2);
//        LinkedListUtils.printLinkedList(res1);
        ListNode res2 = Main.mergeImprove(head1, head2);
        LinkedListUtils.printLinkedList(res2);
    }

}
